package com.chj.gaoji.class03;

public class Code01_MaxPathSum {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int val) {
			value = val;
		}
	}

	public static int maxPathSum(Node head) {
		return process(head).allMaxPathSum;
	}

	public static class Info {
		public int fromHeadMaxPathSum;
		public int allMaxPathSum;

		public Info(int f, int a) {
			fromHeadMaxPathSum = f;
			allMaxPathSum = a;
		}
	}

	public static Info process(Node x) {
		if (x == null) {
			return null;
		}

		Info leftInfo = process(x.left);
		Info rightInfo = process(x.right);

		int p1 = x.value;
		int p2 = x.value + (leftInfo == null ? 0 : leftInfo.fromHeadMaxPathSum);
		int p3 = x.value + (rightInfo == null ? 0 : rightInfo.fromHeadMaxPathSum);

		int fromHeadMaxPathSum = Math.max(Math.max(p2, p1), p3);
		int allMaxPathSum = fromHeadMaxPathSum;
		if (leftInfo != null) {
			allMaxPathSum = Math.max(allMaxPathSum, leftInfo.allMaxPathSum);
		}

		if (rightInfo != null) {
			allMaxPathSum = Math.max(allMaxPathSum, rightInfo.allMaxPathSum);
		}

		return new Info(fromHeadMaxPathSum, allMaxPathSum);
	}

	// for test -- print tree
	public static void printTree(Node head) {
		System.out.println("Binary Tree:");
		printInOrder(head, 0, "H", 17);
		System.out.println();
	}

	public static void printInOrder(Node head, int height, String to, int len) {
		if (head == null) {
			return;
		}
		printInOrder(head.right, height + 1, "v", len);
		String val = to + head.value + to;
		int lenM = val.length();
		int lenL = (len - lenM) / 2;
		int lenR = len - lenM - lenL;
		val = getSpace(lenL) + val + getSpace(lenR);
		System.out.println(getSpace(height * len) + val);
		printInOrder(head.left, height + 1, "^", len);
	}

	public static String getSpace(int num) {
		String space = " ";
		StringBuffer buf = new StringBuffer("");
		for (int i = 0; i < num; i++) {
			buf.append(space);
		}
		return buf.toString();
	}

	public static int getMaxDistance(Node head) {
		return process2(head).maxDistance;
	}

	public static class ReturnType {
		public int maxDistance;
		public int height;

		public ReturnType(int maxDistance, int height) {
			this.maxDistance = maxDistance;
			this.height = height;
		}
	}

	public static ReturnType process2(Node head) {
		if (head == null) {
			return new ReturnType(0, 0);
		}
		ReturnType leftData = process2(head.left);
		ReturnType rightData = process2(head.right);
		int height = Math.max(leftData.height, rightData.height) + 1;
		int maxDistance = Math.max(leftData.height + rightData.height + 1,
				Math.max(leftData.maxDistance, rightData.maxDistance));
		return new ReturnType(maxDistance, height);
	}

	public static int maxPathS(Node head) {
		if (head == null) {
			return 0;
		}
		return func(head).maxPathSum;
	}

	public static class Info2 {
		public int maxPathSum;
		public int headMaxPathSum;

		public Info2(int maxPath, int headMaxPath) {
			maxPathSum = maxPath;
			headMaxPathSum = headMaxPath;
		}
	}

	public static Info2 func(Node x) {
		if (x == null) {
			return null;
		}
		Info2 leftInfo = func(x.left);
		Info2 rightInfo = func(x.right);
		int p1 = Integer.MIN_VALUE;
		if (leftInfo != null) {
			p1 = leftInfo.maxPathSum;
		}
		int p2 = Integer.MIN_VALUE;
		if (rightInfo != null) {
			p2 = rightInfo.maxPathSum;
		}
		int p3 = x.value;
		int p4 = Integer.MIN_VALUE;
		if (leftInfo != null) {
			p4 = x.value + leftInfo.headMaxPathSum;
		}
		int p5 = Integer.MIN_VALUE;
		if (rightInfo != null) {
			p5 = x.value + rightInfo.headMaxPathSum;
		}
		int maxPathSum = Math.max(Math.max(Math.max(p1, p2), p3), Math.max(p4, p5));
		int headMaxPathSum = Math.max(Math.max(p3, p4), p5);
		return new Info2(maxPathSum, headMaxPathSum);
	}

	public static int maxPathSum3(Node head) {
		if (head == null) {
			return 0;
		}
		ReturnType3 allData = process3(head);
		return allData.maxValue < 0 ? allData.maxValue : allData.maxPathSumAll;
	}

	// 每棵子树，执行完递归之后，需要返回的内容
	public static class ReturnType3 {
		public int maxPathSumAll; // 路径最大和
		public int maxPathSumHead;// 含头路径最大和
		public int maxValue; // 先忽略

		public ReturnType3(int all, int fromHead, int max) {
			maxPathSumAll = all;
			maxPathSumHead = fromHead;
			maxValue = max;
		}
	}

	public static ReturnType3 process3(Node x) {
		if (x == null) {
			return new ReturnType3(0, 0, Integer.MIN_VALUE);
		}
		ReturnType3 leftData = process3(x.left);
		ReturnType3 rightData = process3(x.right);
		int maxValue = Math.max(x.value, Math.max(leftData.maxValue, rightData.maxValue));
		int maxPathSumHead = Math.max(leftData.maxPathSumHead, rightData.maxPathSumHead) + x.value;
		maxPathSumHead = Math.max(x.value, maxPathSumHead);
		int maxPathSumAll = Math.max(Math.max(leftData.maxPathSumAll, rightData.maxPathSumAll), maxPathSumHead);
		return new ReturnType3(maxPathSumAll, maxPathSumHead, maxValue);
	}

	public static int maxPathLen(Node head) {
		return func4(head).maxPathLen;
	}

	public static class Data {
		public int height;
		public int maxPathLen;

		public Data(int h, int m) {
			height = h;
			maxPathLen = m;
		}
	}

	public static Data func4(Node x) {
		if (x == null) {
			return null;
		}

		Data leftData = func4(x.left);
		Data rightData = func4(x.right);
		int height = 1 + Math.max(leftData == null ? 0 : leftData.height, rightData == null ? 0 : rightData.height);
		int maxPathLen = 1 + (leftData == null ? 0 : leftData.height) + (rightData == null ? 0 : rightData.height);
		if (leftData != null) {
			maxPathLen = Math.max(maxPathLen, leftData.maxPathLen);
		}

		if (rightData != null) {
			maxPathLen = Math.max(maxPathLen, rightData.maxPathLen);
		}

		return new Data(height, maxPathLen);
	}

	public static void main(String[] args) {
		Node head = new Node(4);
		head.left = new Node(1);
		head.left.right = new Node(5);
		head.right = new Node(-7);
		head.right.left = new Node(3);

		Node head1 = new Node(1);
		head1.left = new Node(2);
		head1.right = new Node(3);
		head1.left.left = new Node(4);
		head1.left.right = new Node(5);
		head1.right.left = new Node(6);
		head1.right.right = new Node(7);
		head1.left.left.left = new Node(8);
		head1.right.left.right = new Node(9);

		System.out.println("maxPathSum");
		System.out.println(maxPathSum(head));
		System.out.println(maxPathSum(head1));

		System.out.println("getMaxDistance");
		System.out.println(getMaxDistance(head));
		System.out.println(getMaxDistance(head1));

		System.out.println("maxPathS");
		System.out.println(maxPathS(head));
		System.out.println(maxPathS(head1));

		System.out.println("maxPathSum3");
		System.out.println(maxPathSum3(head));
		System.out.println(maxPathSum3(head1));

		System.out.println("maxPathLen");
		System.out.println(maxPathLen(head));
		System.out.println(maxPathLen(head1));
	}
}
